Image segmentation is an initial step in many image processing tasks such as pattern recognition, image coding and image interpretation. For example, in scene understanding applications, the segmentation process generally provides a labelling process with regions to be classified.
The publication entitled “Digital Image Processing” by Rafael C. Gonzalez and Richard E. Woods, Addison-Wesley Publishing Company 1993 discloses on page 461–465, a method for image segmentation. This method utilizes a region splitting and merging procedure. This procedure subdivides an image initially into a set of arbitrary, disjointed regions and then merges and/or splits the regions depending whether the regions satisfy a certain homogeneity criteria. Typically, the homogeneity criterion is based on a threshold value arbitrarily selected by a user. However, this method suffers from the disadvantage that the choice of threshold values is critical for successful image segmentation. Specifically, a particular threshold value may work with one image but not necessarily with others. For example, this method often fails to split regions that must be separated or fails to merge regions that need not be separated. This is a consequence of the information about the uniformity in a region corresponding to an object surface and the discontinuity between regions corresponding to different object surfaces not being easily incorporated into the method.
The publication entitled “Seeded Region Growing” IEEE Trans. Pattern Anal Machine Intell., vol. 16 pp. 641–647, 1994 (hereinafter called Adams et al) discloses a method for segmentation of images. The Adams method is based on a region growing principle of selecting a pixel adjacent to a region of pixels, which is most similar to the region of pixels. The method does not rely on the arbitrary selection of homogeneity thresholds, but is controlled by choosing a small number of pixels, called seeds. This seed selection may be either automatic or manual. Once the seeds have been selected, the segmented regions are grown in an iterative fashion. Adams suggest using an automatic converging squares method for seeds selection. Adams uses this method to locate objects of minimum and maximum intensity in biomedical images. Each step of the Adam method involves the addition of one of the neighboring pixels to one of the regions grown from the seeds. A measure δ(x) is defined how different each of the neighboring pixels is from that region. The neighboring pixel having the minimum measure δ(x) is added to the region. Adams et al make use of a sorted list in determining the relevant neighboring pixel to be added. In Adams et al, once a pixel has been added to the list, the δ(x) measure is never updated. However, this method is not successful for images where the number of regions is large and the regions have diverse characteristics. Moreover, the Adams et al method suffers from the disadvantage of slow image segmentation. Whilst, this method is robust and easy-to-use, it also suffers from the disadvantage that the resultant segmented image is stored as a pixel-map representation and as such is memory consuming and not efficient for feature computation.